package com.acwing.partition10;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/1/9 13:08
 */
public class AC903昂贵的聘礼 {

    private static final int N = 110, INF = 0x3f3f3f3f;
    private static int[][] graph = new int[N][N];
    private static int[] level = new int[N];
    private static int n = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        int limited = Integer.parseInt(s[0]);
        n = Integer.parseInt(s[1]);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) graph[i][j] = i == j ? 0 : INF;
        }
        for (int i = 1; i <= n; i++) {
            //读入每个物品的直接价格、主人的等级、代替物品数
            s = reader.readLine().split("\\s+");
            int price = Integer.parseInt(s[0]), replace = Integer.parseInt(s[2]);
            level[i] = Integer.parseInt(s[1]);
            graph[0][i] = price;
            for (int j = 0; j < replace; j++) {
                s = reader.readLine().split("\\s+");
                //读入代替物品的编号和使用该物品后的优惠价格
                int id = Integer.parseInt(s[0]), cost = Integer.parseInt(s[1]);
                //代替物品向主物品连条边，权值就是优惠后的价格，而所有不使用代替物品的物品都从超级源点0出发
                graph[id][i] = Math.min(graph[id][i], cost);
            }
        }
        int answer = INF;
        //枚举每个合法的等级范围，在合法的等级范围内进行dijkstra
        for (int i = level[1] - limited; i <= level[1]; i++) answer = Math.min(answer, dijkstra(i, i + limited));
        writer.write(answer + "\n");
        writer.flush();
    }

    private static int dijkstra(int left, int right) {
        //从超级源点出发，在等级范围内找最短路
        int[] dist = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        for (int i = 0; i <= n; i++) dist[i] = INF;
        dist[0] = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j <= n; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;
            }
            visited[u] = true;
            for (int j = 0; j <= n; j++) {
                if (level[j] < left || level[j] > right) continue;
                dist[j] = Math.min(dist[j], dist[u] + graph[u][j]);
            }
        }
        return dist[1];
    }
}
